<h2>题目编号 : 219</h2>
<div style="color:#666;font-size:80%;">29 November 2008</div><br />
<div class="problem_content">
<p>Let <span style="font-weight:bold">A</span> and <span style="font-weight:bold">B</span> be bit strings (sequences of 0's and 1's).<br />
If <span style="font-weight:bold">A</span> is equal to the <span style="text-decoration:underline;">left</span>most length(<span style="font-weight:bold">A</span>) bits of <span style="font-weight:bold">B</span>, then <span style="font-weight:bold">A</span> is said to be a <span style="font-style:italic">prefix</span> of <span style="font-weight:bold">B</span>.<br />
For example, 00110 is a prefix of <span style="text-decoration:underline;">00110</span>1001, but not of 00111 or 100110.</p>

<p>A <span style="font-style:italic">prefix-free code of size</span> <var>n</var> is a collection of <var>n</var> distinct bit strings such that no string is a prefix of any other.  For example, this is a prefix-free code of size 6:</p>

<p style="text-align:center;">0000, 0001, 001, 01, 10, 11</p>

<p>Now suppose that it costs one penny to transmit a '0' bit, but four pence to transmit a '1'.<br />
Then the total cost of the prefix-free code shown above is 35 pence, which happens to be the cheapest possible for the skewed pricing scheme in question.<br />
In short, we write Cost(6) = 35.</p>

<p>What is Cost(10<img src="" style="display:none;" alt="^(" /><sup>9</sup><img src="" style="display:none;" alt=")" />) ?</p>
</div><br />
